/**
 * [0, n]满足条件的数，条件为：
 * 二进制不含连续的1
 * 
 */
using llt = long long;

vector<int> G;
// Dij表示搜索到i位前一位为j的数量
llt D[35][2];
llt dfs(int pos, int pre, bool lead, bool limit){
    if(-1 == pos) {
        return 1;   // 到底了就是1，因为0也可以计算
    }
    if(not lead and not limit and -1 != D[pos][pre]) {
        return D[pos][pre];
    }
    int last = limit ? G[pos] : 1;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        if(1 == i and 1 == pre) continue;

        ans += dfs(pos - 1, i, lead&&i==0, limit&&i==last);        
    }
    if(not lead and not limit){
        D[pos][pre] = ans;
    }    
    return ans;
}

llt digitDP(llt n){
    G.clear();
    while(n){
        G.emplace_back(n % 2);
        n /= 2;
    }
    return dfs(G.size()-1, 0, true, true);
}

class Solution {
public:
    int findIntegers(int n) {
        memset(D, -1, sizeof(D));
        return digitDP(n);
    }
};